package com.xiaolin.algorithm.search.fibonacci;

import java.util.Arrays;

/**
 * @ClassName FibonacciSearch
 * @Description 斐波那契查找
 * @Detail 斐波那契数列   当n=1时，f(n)=1，当n=2时，f(n)=1，当n>2时，f(n)=f(n-1)+f(n-2)
 *          满足斐波那契数列的数组  f(n)-1=(f(n-1)-1)+(f(n-2)-1)+1
 * @Author MyPC
 * @Date 2020/11/17
 * @Version 1.0
 */
public class FibonacciSearch {


    /**
     * 查找元素
     * @param arr
     * @param ele
     * @return
     */
    public int search(int[] arr,int ele){

        // 1、将数组扩容到符合斐波那契比例
        // 1.1 获取斐波那契数列
        int[] f = fibonacciList(10);
        int index=0;
        int first=0;
        int last=arr.length-1;
        // 1.2 找到大于或等于数组长度的最小的斐波那契数列中的值
        while (arr.length> f[index]){
            index++;
        }
        // 1.3 如果数组长度小于斐波那契数列中的值-1，那么需要对原数组进行拷贝
        // 新数组的长度
        int newArrLength=f[index]-1;
        int[] temp=new int[newArrLength];
        int i=0;
        // 1.3.1 拷贝
        while (i<=arr.length-1){
            temp[i]=arr[i];
            i++;
        }
        if(arr.length < newArrLength){
            // 1.3.2 将新数组多余的0值填充为原数组最后一个元素的值
            for(int j=arr.length;j<newArrLength;j++){
                temp[j]=arr[arr.length-1];
            }
        }
        //2、 循环查找元素
        while (first <= last){
            // 满足斐波那契数列的数组，分割之后依然满足，就算只剩下一个元素，也是满足要求
            int mid=first+f[index-1]-1;
            if(ele < temp[mid]){
                // 查找左边的元素
                last=mid-1;
                // 取f(n-1)那段斐波那契数列
                index--;
            }else if(ele > temp[mid]){
                // 查找右边元素
                first=mid+1;
                // 取f(n-2)那段斐波那契数列
                index-=2;
            }else {
                //找到元素
                if(mid<=last){
                    // 说明找到的元素在原数组范围内
                    return mid;
                }else {
                    // 说明找到的元素在新数组超出原数组部分的那段范围内，则取原数组最后一个元素即可，因为最后一个元素与超出部分元素是相等的
                    return last;
                }
            }
        }
        // 找不到返回-1
        return -1;
    }

    /**
     * 获取斐波那契数组
     * @param size
     * @return
     */
    public int[] fibonacciList(int size){
        int[] f=new int[size];
        f[0]=1;
        f[1]=1;
        for (int i=2;i<f.length;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }

}
